package code;

import java.util.Collections;
import java.util.concurrent.ConcurrentHashMap;

public class DLX {

	public DLX(){
		
	}
	
	class LinkNode{
		int value;
		int colNo;
		LinkNode left;
		LinkNode right;
		LinkNode up;
		LinkNode down;
		LinkNode(){
			
		}
		LinkNode(int val,LinkNode l,LinkNode r,LinkNode u,LinkNode d){
			value=val;
			left=l;
			right=r;
			up=u;
			down=d;
		}
	}
	char[][] xboard={{'.','.','.','.','.','7','.','.','9'},
			{'.','4','.','.','8','1','2','.','.'},
			{'.','.','.','9','.','.','.','1','.'},
			{'.','.','5','3','.','.','.','7','2'},
			{'2','9','3','.','.','.','.','5','.'},
			{'.','.','.','.','.','5','3','.','.'},
			{'8','.','.','.','2','3','.','.','.'},
			{'7','.','.','.','5','.','.','4','.'},
			{'5','3','1','.','7','.','.','.','.'}};
	/*
	 * 整个矩阵的列的head
	 * colHead[]列的头部
	 */
	LinkNode head;
	LinkNode[] colHead;
	int row=729;
	int col=324;
	int[] colCnt;
	
	/*
	 * 81*9行，324列的矩阵
	 * 初始化矩阵
	 */
	void init(){
		int i,j;
		/*
		 *初始化head
		 */
		head=new LinkNode();
		head.left=head;
		head.right=head;
		head.up=head;
		head.down=head;
		/*
		 * 初始化列头
		 */
		colHead=new LinkNode[col];
		for(i=0;i<col;i++){
			colHead[i]=new LinkNode();
			/*
			 * value代表列号
			 */
			colHead[i].colNo=i;
			
			colHead[i].down=colHead[i];
			colHead[i].up=colHead[i];
			if(i==0){
				head.right=colHead[i];
				colHead[i].right=head;
				colHead[i].left=head;
				head.left=colHead[i];
			}
			else{
				colHead[i].left=colHead[i-1];
				colHead[i-1].right=colHead[i];
				colHead[i].right=head;
				head.left=colHead[i];
			}
		}
		colCnt=new int[col];
		/*
		 * 初始化行
		 * 9*9*9
		 */
		for(i=0;i<9;i++){
			for(j=0;j<9;j++){
				/*
				 * 数独[i][j]位置放k+1，对应的行号为81*i+9*j+k
				 * 同时对应的列需要
				 * 第一个81列表示[i][j]号格子，对应列号：9*i+j
				 * 第二个9*9列代表第i行，k元素，对应列号：81+9*i+k
				 * 第三个9*9列代表第j列，k元素，对应列号:81+81+9*j+k
				 * 第四个9*9类代表小3X3矩阵，k元素，对应的列号：81*3+(i/3*3+j/3)*9+k
				 */
				if(xboard[i][j]!='.'){
					/*
					 * [i][j]已经填好了board[i][j]-'0'
					 */
					int k=(int)(xboard[i][j]-'1');
					LinkNode nodeA=new LinkNode();
					nodeA.value=i*81+9*j+k;
					nodeA.colNo=colHead[9*i+j].colNo;
					
					nodeA.down=colHead[9*i+j];
					colHead[9*i+j].up.down=nodeA;
					nodeA.up=colHead[9*i+j].up;
					colHead[9*i+j].up=nodeA;
					
					nodeA.left=nodeA;
					nodeA.right=nodeA;
					colCnt[9*i+j]++;
					
					/*
					 * 第2个1，对应的列号：81+9*i+k
					 */
					LinkNode nodeB=new LinkNode();
					nodeB.value=i*81+9*j+k;
					nodeB.colNo=colHead[81+9*i+k].colNo;
					
					nodeB.down=colHead[81+9*i+k];
					colHead[81+9*i+k].up.down=nodeB;
					nodeB.up=colHead[81+9*i+k].up;
					colHead[81+9*i+k].up=nodeB;
					
					nodeA.right=nodeB;
					nodeB.left=nodeA;
					nodeB.right=nodeA;
					nodeA.left=nodeB;
					colCnt[81+9*i+k]++;
					
					/*
					 *第3个1，对应的列好：162+j+k
					 */
					LinkNode nodeC=new LinkNode();
					nodeC.value=i*81+9*j+k;
					nodeC.colNo=colHead[162+9*j+k].colNo;
					
					nodeC.down=colHead[162+9*j+k];
					colHead[162+9*j+k].up.down=nodeC;
					nodeC.up=colHead[162+9*j+k].up;
					colHead[162+9*j+k].up=nodeC;
					
					nodeB.right=nodeC;
					nodeC.left=nodeB;
					nodeC.right=nodeA;
					nodeA.left=nodeC;
					colCnt[162+9*j+k]++;
					
					/*
					 * 第4个1，对应的列号：243+(i/3*3+j/3)+k
					 */
					LinkNode nodeD=new LinkNode();
					nodeD.value=i*81+9*j+k;
					nodeD.colNo=colHead[243+(i/3*3+j/3)*9+k].colNo;
					
					nodeD.down=colHead[243+(i/3*3+j/3)*9+k];
					colHead[243+(i/3*3+j/3)*9+k].up.down=nodeD;
					nodeD.up=colHead[243+(i/3*3+j/3)*9+k].up;
					colHead[243+(i/3*3+j/3)*9+k].up=nodeD;
					
					nodeC.right=nodeD;
					nodeD.left=nodeC;
					nodeD.right=nodeA;
					nodeA.left=nodeD;
					colCnt[243+(i/3*3+j/3)*9+k]++;
					
					continue;
				}
				/*
				 * 若为.则需生成9（k=1~9）个行来覆盖
				 */
				for(int k=0;k<9;k++){
					/*
					 * 生成第一个1，对应的列号：9*i+j
					 */
					LinkNode nodeA=new LinkNode();
					nodeA.value=i*81+9*j+k;
					nodeA.colNo=colHead[9*i+j].colNo;
					
					nodeA.down=colHead[9*i+j];
					colHead[9*i+j].up.down=nodeA;
					nodeA.up=colHead[9*i+j].up;
					colHead[9*i+j].up=nodeA;
					
					nodeA.left=nodeA;
					nodeA.right=nodeA;
					colCnt[9*i+j]++;
					
					/*
					 * 第2个1，对应的列号：81+9*i+k
					 */
					LinkNode nodeB=new LinkNode();
					nodeB.value=i*81+9*j+k;
					nodeB.colNo=colHead[81+9*i+k].colNo;
					
					nodeB.down=colHead[81+9*i+k];
					colHead[81+9*i+k].up.down=nodeB;
					nodeB.up=colHead[81+9*i+k].up;
					colHead[81+9*i+k].up=nodeB;
					
					nodeA.right=nodeB;
					nodeB.left=nodeA;
					nodeB.right=nodeA;
					nodeA.left=nodeB;
					colCnt[81+9*i+k]++;
					
					/*
					 *第3个1，对应的列好：162+j+k
					 */
					LinkNode nodeC=new LinkNode();
					nodeC.value=i*81+9*j+k;
					nodeC.colNo=colHead[162+9*j+k].colNo;
					
					nodeC.down=colHead[162+9*j+k];
					colHead[162+9*j+k].up.down=nodeC;
					nodeC.up=colHead[162+9*j+k].up;
					colHead[162+9*j+k].up=nodeC;
					
					nodeB.right=nodeC;
					nodeC.left=nodeB;
					nodeC.right=nodeA;
					nodeA.left=nodeC;
					colCnt[162+9*j+k]++;
					
					/*
					 * 第4个1，对应的列号：243+(i/3*3+j/3)+k
					 */
					LinkNode nodeD=new LinkNode();
					nodeD.value=i*81+9*j+k;
					nodeD.colNo=colHead[243+(i/3*3+j/3)*9+k].colNo;
					
					nodeD.down=colHead[243+(i/3*3+j/3)*9+k];
					colHead[243+(i/3*3+j/3)*9+k].up.down=nodeD;
					nodeD.up=colHead[243+(i/3*3+j/3)*9+k].up;
					colHead[243+(i/3*3+j/3)*9+k].up=nodeD;
					
					nodeC.right=nodeD;
					nodeD.left=nodeC;
					nodeD.right=nodeA;
					nodeA.left=nodeD;
					colCnt[243+(i/3*3+j/3)*9+k]++;
					
				}
			}
		}
	}
	
	/*
	 * 将c列删除
	 */
	void remove(int c){
		/*
		 * 先从colHead[c]删除c
		 */
		colHead[c].left.right=colHead[c].right;
		colHead[c].right.left=colHead[c].left;
		/*
		 * 将c列下的所有行都删除
		 */
		for(LinkNode u=colHead[c].down;u!=colHead[c];u=u.down){
			for(LinkNode v=u.right;v!=u;v=v.right){
				/*
				 * 删除节点v
				 */
				v.up.down=v.down;
				v.down.up=v.up;
			}
		}
	}
	/*
	 * 恢复删除的c列
	 */
	void resume(int c){
		/*
		 * 先colhead[c]
		 */
		colHead[c].left.right=colHead[c];
		colHead[c].right.left=colHead[c];
		/*
		 * 将c列下的所有行恢复
		 */
		for(LinkNode u=colHead[c].up;u!=colHead[c];u=u.up){
			for(LinkNode v=u.left;v!=u;v=v.left){
				/*
				 * 恢复节点v
				 */
				v.up.down=v;
				v.down.up=v;
			}
		}
	}
	
	/*
	 * 搜索函数,返回step的大小，行数
	 */
	int danceLink(int[] rec,int step){
		/*
		 * 判断整个矩阵是否处理完,判断所有的列是否已处理完
		 */
		if(head.right==head)
			return step;
		/*
		 * 选择1个数最少的列c,删除c
		 */
		int minCol=Integer.MAX_VALUE;
		int c=0;
		for(LinkNode u=head.right;u!=head;u=u.right){
			if(minCol>colCnt[u.colNo]){
				minCol=colCnt[u.colNo];
				c=u.colNo;
			}
		}
		/*
		 * 虽然不会出现以下情况，但是还是考虑
		 */
		if(minCol==Integer.MAX_VALUE){
			return -1;
		}
		/*
		 * 删除c
		 */
		remove(c);
		/*
		 * 枚举覆盖的c列的行
		 */
		for(LinkNode u=colHead[c].down;u!=colHead[c];u=u.down){
			/*
			 * 选择u行来覆盖c列
			 */
			rec[step]=u.value;
			/*
			 * 删除u行覆盖的其他列
			 */
			for(LinkNode v=u.right;v!=u;v=v.right){
				remove(v.colNo);
			}
			int temp=danceLink(rec,step+1);
			if(temp!=-1){
				return temp;
			}
			/*
			 * 恢复u行覆盖的其他列
			 */
			for(LinkNode v=u.left;v!=u;v=v.left){
				resume(v.colNo);
			}
		}
		/*
		 * 恢复c列
		 */
		resume(c);
		return -1;
	}
	void solved(){
		Collections;
		HashMap;
		Set;
		ArrayList
		ConcurrentHashMap<>() cmp=new ConcurrentHashMap<>();
		init();
		int[] rec=new int[row];
		int step=0;
		step=danceLink(rec,0);
		if(step==-1){
			System.out.println("未找到解！");
		}
		for(int i=0;i<step;i++){
			int x=rec[i]/81;
			int y=(rec[i]-81*x)/9;
			xboard[x][y]=(char)(rec[i]%9+'1');
		}
		for(int i=0;i<9;i++){
			for(int j=0;j<9;j++){
				System.out.print(" "+xboard[i][j]+" ");
			}
			System.out.println();
		}
	}
    public void solveSudoku(char[][] board) {
    	this.xboard=board;
		init();
		int[] rec=new int[row];
		int step=0;
		step=danceLink(rec,0);
		if(step==-1){
			System.out.println("未找到解！");
		}
		for(int i=0;i<step;i++){
			int x=rec[i]/81;
			int y=(rec[i]-81*x)/9;
			board[x][y]=(char)(rec[i]%9+'1');
		}
//		for(int i=0;i<9;i++){
//			for(int j=0;j<9;j++){
//				System.out.print(" "+board[i][j]+" ");
//			}
//			System.out.println();
//		}
    }
    
	public static void main(String[] args){
		new DLX().solved();
	}
}
